package BFS解决FloodFill算法.多源;

import java.util.LinkedList;
import java.util.Queue;

// 给一个矩阵，找出1到0的最短的位置
//  正难则反，我们可以直接先把所有0加入到队列然后探索0到1的位置
public class 矩阵找出1到0的最短位置 {

    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};
    public int[][] updateMatrix(int[][] matrix) {
         int m = matrix.length;
         int n = matrix[0].length;
         int [][] dist = new int [m][n];
        for(int i = 0 ;i<m;i++)
        {
            for(int j = 0 ; j<n;j++)
            {
                dist[i][j] = -1;
            }
        }
        Queue<int []> q = new LinkedList<>();
        // 1.把所有的源点加入到队列里
        for(int i = 0 ;i<m;i++)
        {
            for(int j = 0 ; j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    dist[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }
        // 2.一层一层往外扩
        while(!q.isEmpty())
        {
            int [] cur =q.poll();
            int a = cur[0],b= cur[1];
            for(int i = 0;i<4;i++)
            {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x>=0 && x<m && y>=0&& y<n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b]+1;
                    q.add(new int[]{x,y});
                }
            }
        }

        return dist;
    }
}
